class Task32_3:
    def run(self, tree):
        stack1 = []
        stack2 = []
        result = []

        if tree is not None:
            stack1.append(tree)

        left_to_right = True
        while len(stack1) + len(stack2) > 0:
            layer = []
            while len(stack1) > 0:
                node = stack1.pop()
                layer.append(node.val)
                if left_to_right:
                    if node.left is not None:
                        stack2.append(node.left)
                    if node.right is not None:
                        stack2.append(node.right)
                else:
                    if node.right is not None:
                        stack2.append(node.right)
                    if node.left is not None:
                        stack2.append(node.left)
            result.append(layer)
            stack1 = stack2
            stack2 = []
            left_to_right = not left_to_right

        return result
